package nowcoder.offer;

import java.util.ArrayList;

/**
 * 机器人的运动范围
 *
 * @author briarbear
 * @blog https://briarbear.github.io
 * @date 2018-08-30 16:09
 */
public class MovingCount {

    int[][] path;
    int rows;
    int cols;

    /**
     * 动态规划
     */
    public int solution(int threshold,int rows,int cols){
        if (threshold < 0 || rows < 0 || cols < 0 ) return 0;
        path = new int[rows][cols];
        int[][] martix = new int[rows][cols];
        block(rows,cols,threshold);
        this.rows = rows;
        this.cols = cols;
        //path[i][j] == 1 ,表示可到达
        path[0][0] = 1;
        for(int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (path[i][j] != 0) continue;
                if (j > 0 && path[i][j-1] == 1){
                    path[i][j] = 1;  //左
                    continue;
                }
                if (i > 0 && path[i-1][j] == 1){
                    path[i][j] = 1; //上
                    continue;
                }

            }
        }


        for (int i = rows-1; i >=0 ; i--) {
            for (int j = cols-1; j >=0 ; j--) {
                if (path[i][j] != 0) continue;

                if (j < cols-1 && path[i][j+1] == 1){
                    path[i][j] = 1; //右
                    continue;
                }
                if (i < rows-1 && path[i+1][j] == 1){
                    path[i][j] = 1;  //下
                    continue;
                }
            }
        }
        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (path[i][j] == 1)
                    count++;
            }
        }

        return count;
    }




    public void block(int rows,int cols,int k){
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                char[] ci = String.valueOf(i).toCharArray();
                char[] cj = String.valueOf(j).toCharArray();
                int sum = 0;
                for (int l = 0; l < ci.length; l++) {
                    sum += ci[l] - '0';
                }
                for (int l = 0; l < cj.length; l++) {
                    sum += cj[l] - '0';
                }
                if (sum > k) path[i][j] = -1;  //有障碍物的情况
            }
        }
    }


    /**
     * 深度搜索
     */

    public int solution2(int threshold,int rows,int cols){
        int flag[][] = new int[rows][cols];
        return helper(0,0,rows,cols,flag,threshold);
    }

    private int helper(int i,int j,int row,int cols,int[][] flag,int threshold){
        if (i < 0 || i > row-1 || j < 0 || j > cols-1 || sum(i) + sum(j) > threshold || flag[i][j] == 1)
            return 0;
        flag[i][j] = 1;
        return  helper(i+1,j,row,cols,flag,threshold) +
                helper(i,j+1,row,cols,flag,threshold) +
                helper(i-1,j,row,cols,flag,threshold) +
                helper(i,j-1,row,cols,flag,threshold) + 1;
    }

    private int sum(int i){
        int res = 0;
        while (i > 0){
            res += i / 10;
            i /= 10;
        }
        return res;
    }


    public static void main(String[] args) {
        new MovingCount().solution(5,10,10);
    }
}
